package linkedlist.pro;

import linkedlist.ListNode;

/**
 * @Classname : PalindromeLinkedList
 * @Description :
 * <a href="https://leetcode.cn/problems/palindrome-linked-list/">234. 回文链表</a>
 * @Author : chentianyu
 * @Date 2022/12/25 22:04
 */


public class PalindromeLinkedList {
    public boolean isPalindrome(ListNode head) {
        // 通过快慢指针先找到链表的中点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 对中点至末尾链表进行反转
        slow = reverseList(slow);
        // 比对判断原链表是否为回文链表
        fast = head;
        while (fast != null && slow != null) {
            if (fast.val != slow.val) return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    private ListNode reverseList(ListNode head) {
        ListNode next = head, pre = null;
        while (next != null) {
            ListNode cur = next;
            next = cur.next;
            cur.next = pre;
            pre = cur;
        }
        return pre;
    }
}
